Maximum subarray

Time: O(N); Space: O(1); medium

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation:

  • [4,-1,2,1] has the largest sum = 6.

Example2:

Input: nums = [1,2,3,4]

Output: 10

Explanation:

  • The contiguous subarray [1,2,3,4] has the largest sum = 10.

Follow up:

  • If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

[3]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result, curr = float("-inf"), float("-inf")

        for x in nums:
            curr = max(curr+x, x)
            result = max(result, curr)

        return result

[4]:

s = Solution1()

nums = [-2,1,-3,4,-1,2,1,-5,4]
assert s.maxSubArray(nums) == 6

nums = nums = [1,2,3,4]
assert s.maxSubArray(nums) == 10